{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Paint Fence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #栅栏涂色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>k</code> 种颜色的涂料和一个包含 <code>n</code> 个栅栏柱的栅栏，请你按下述规则为栅栏设计涂色方案：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个栅栏柱可以用其中 <strong>一种</strong> 颜色进行上色。</li>\n",
    "\t<li>相邻的栅栏柱 <strong>最多连续两个 </strong>颜色相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个整数 <code>k</code> 和 <code>n</code> ，返回所有有效的涂色 <strong>方案数</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/28/paintfenceex1.png\" style=\"width: 507px; height: 313px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>所有的可能涂色方案如上图所示。注意，全涂红或者全涂绿的方案属于无效方案，因为相邻的栅栏柱 <strong>最多连续两个 </strong>颜色相同。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, k = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, k = 2\n",
    "<strong>输出：</strong>42\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 50</code></li>\n",
    "\t<li><code>1 <= k <= 10<sup>5</sup></code></li>\n",
    "\t<li>题目数据保证：对于输入的 <code>n</code> 和 <code>k</code> ，其答案在范围 <code>[0, 2<sup>31</sup> - 1]</code> 内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [paint-fence](https://leetcode.cn/problems/paint-fence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [paint-fence](https://leetcode.cn/problems/paint-fence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n2', '1\\n1', '7\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#       1   2\n",
    "# same  k   k       k(k-1)\n",
    "#       2   2       2\n",
    "# diff      k(k-1)  k(k-1) + k(k-1)(k-1)\n",
    "#           2       2 + 2\n",
    "#\n",
    "# next_same = diff\n",
    "# next_diff = same * (k-1) + diff * (k-1)\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        if k == 1:\n",
    "            return (1 if n == 2 else 0)\n",
    "\n",
    "        same = k\n",
    "        diff = k * (k - 1)\n",
    "        for i in range(3, n + 1):\n",
    "            next_same = diff\n",
    "            next_diff = same * (k - 1) + diff * (k - 1)\n",
    "            same, diff = next_same, next_diff\n",
    "        \n",
    "        return same + diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        dp = [0] * n\n",
    "        dp[0] = k\n",
    "        dp[1] = k * k\n",
    "        for i in range(2, n):\n",
    "            dp[i] = dp[i - 1] * (k-1) + dp[i - 2] * (k-1)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        same, different = 0, k\n",
    "        for i in range(1,n):\n",
    "            same, different = different, (same + different) * (k - 1)\n",
    "        return different + same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        \n",
    "        same_result = [0] * n\n",
    "        diff_result = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                same_result[i] = k\n",
    "                diff_result[i] = k\n",
    "            elif i == 1:\n",
    "                same_result[i] = k\n",
    "                diff_result[i] = k * (k - 1)\n",
    "            else:\n",
    "                same_result[i] = diff_result[i - 1]\n",
    "                diff_result[i] = same_result[i - 1] * (k - 1) + diff_result[i - 1] * (k - 1)\n",
    "        \n",
    "        return same_result[-1] + diff_result[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return k\n",
    "        if n==2:\n",
    "            return k*k\n",
    "        total=[0]*n\n",
    "        total[0]=k\n",
    "        total[1]=k**2\n",
    "        for i in range(2,n):\n",
    "            total[i]=total[i-1]*(k-1)+total[i-2]*(k-1)\n",
    "        return total[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [ 0 ] * 2\n",
    "        dp[0], dp[1] = 0, k\n",
    "        for i in range(1, n):\n",
    "            dp[0], dp[1] = dp[1], (dp[0] + dp[1]) * ( k - 1 )\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1: return k\n",
    "        if n == 2: return k*k\n",
    "        dp = [0] * n\n",
    "        dp[0] = k\n",
    "        dp[1] = k * k\n",
    "\n",
    "        for i in range(2, n):\n",
    "            dp[i] = (k-1) * (dp[i-1] + dp[i-2])\n",
    "\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        # 用 dp[i][0] 表示到第 i 个柱子为止，且第i-1个柱子的颜色不一样的方案数；\n",
    "        # dp[i][1] 表示和第 i-1 个一样时，到第i个为止的方案数\n",
    "        # 显然要求的是 dp[i][0]+dp[i][1]\n",
    "        # dp[i][0] = (k-1)*(dp[i-1][0]+dp[i-1][1])\n",
    "        # dp[i][1] = dp[i-1][0]\n",
    "        # 令初始化 dp[0][0] = k, dp[0][1]=0\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        dp[0][0] = k\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = (k-1)*(dp[i-1][0]+dp[i-1][1])\n",
    "            dp[i][1] = dp[i-1][0]\n",
    "        return sum(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "\n",
    "        two_back, one_back = k, k**2\n",
    "        for i in range(3, n + 1):\n",
    "            cur = (k - 1) * (two_back + one_back)\n",
    "            two_back = one_back\n",
    "            one_back = cur\n",
    "\n",
    "        return one_back\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dp0, dp1 = k, k*k\n",
    "        if n==1:return dp0\n",
    "        for _ in range(2,n):\n",
    "            dp0, dp1 = dp1, (k-1)*(dp0+dp1)\n",
    "        return dp1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        a, b = k, k**2\n",
    "        for i in range(n-2):\n",
    "            a, b = b, (k-1)*(a+b)\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        if n == 2:\n",
    "            return k + k * (k-1)\n",
    "        dp = [k, k*(k-1)]\n",
    "        for i in range(3, n+1):\n",
    "            dp[0], dp[1] = dp[1], (dp[0] + dp[1]) * (k-1)\n",
    "        return dp[0] + dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        elif n == 2:\n",
    "            return k * k\n",
    "        \n",
    "        # 定义两个变量，分别代表涂色与前一个颜色相同和不同的方案数\n",
    "        same, diff = k, k * (k - 1)\n",
    "        \n",
    "        for i in range(3, n + 1):\n",
    "            # 当前与前一个颜色相同的方案数取决于前一个与再前一个颜色不同的方案数\n",
    "            new_same = diff\n",
    "            # 当前与前一个颜色不同的方案数取决于前一个方案的总数乘以剩余的颜色选择\n",
    "            new_diff = (same + diff) * (k - 1)\n",
    "            same, diff = new_same, new_diff\n",
    "            \n",
    "        return same + diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return k\n",
    "        dp= [0]*n\n",
    "        dp[0]=k\n",
    "        dp[1]=k*k\n",
    "        for i in range(2,n):\n",
    "            dp[i]=(k-1)*(dp[i-1]+dp[i-2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        dp[0][1] = k\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i - 1][1]\n",
    "            dp[i][1] = dp[i - 1][0] * (k - 1) + dp[i - 1][1] * (k - 1)\n",
    "        return sum(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        continous, discrete = 0, k\n",
    "\n",
    "        for i in range(1, n):\n",
    "            continous, discrete = (\n",
    "                discrete,\n",
    "                (continous + discrete) * (k - 1)\n",
    "            )\n",
    "\n",
    "        return continous + discrete"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        dp = [ 0 ] * 2\n",
    "        dp[0] = 0\n",
    "        dp[1] = k\n",
    "        for i in range(1, n):\n",
    "            dp[0], dp[1] = dp[1], (dp[0] + dp[1]) * ( k - 1 )\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n==1: return k\n",
    "        if n==2: return k*k\n",
    "        dp=[0]*n\n",
    "        #初始化\n",
    "        dp[0]=k\n",
    "        dp[1]=k*k\n",
    "        for i in range(2,n):\n",
    "            dp[i]=dp[i-1]*(k-1)+dp[i-2]*(k-1)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        if n == 2:\n",
    "            return k*k\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1] = k\n",
    "        dp[2] = k*k\n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = (k-1)*(dp[i-1]+dp[i-2])\n",
    "        return dp[n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dp = [k, k*k]\n",
    "\n",
    "        for i in range(2, n):\n",
    "            dp.append((dp[i-1] + dp[i-2]) * (k-1))\n",
    "\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if not n or not k: return 0\n",
    "\n",
    "        same, diff = 0, k\n",
    "        for i in range(1,n):\n",
    "            s,d = same, diff\n",
    "            same = d\n",
    "            diff = (k-1)*(s+d)\n",
    "        return same+diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if not n or not k: return 0\n",
    "\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        dp[0] = [k, 0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = (k - 1) * sum(dp[i - 1])\n",
    "            dp[i][1] = dp[i - 1][0]\n",
    "\n",
    "        return sum(dp[n - 1])\n",
    "\n",
    "# 作者：学废了的Kai\n",
    "# 链接：https://leetcode.cn/problems/paint-fence/solutions/314784/python-dong-tai-gui-hua-zhuang-tai-ya-suo-by-cra2y/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i==0:return k\n",
    "            if i==1: return k*k\n",
    "            return (k-1)*f(i-1)+(k-1)*f(i-2)\n",
    "        return f(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        对于给第i个栅栏涂色，考虑3种情况：\n",
    "        1. i - 1 和 i - 2颜色相同，但是i和i - 1颜色不同，则i可以有k - 1种选择\n",
    "        2. i - 1 和 i - 2颜色不同，但是i和i - 1颜色相同，则i只有1种选择\n",
    "        3. i - 1 和 i - 2颜色不同，但是i和i - 1颜色不同，则i可以有k - 1种选择\n",
    "\n",
    "        dp[i][0] := i和 i - 1颜色相同的方案数 = dp[i - 1][1]\n",
    "        dp[i][1] := i和 i - 1颜色不同的方案数 = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)\n",
    "\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "\n",
    "        dp[0][0] = 0 # 前面没有柱子，颜色不可能相同\n",
    "        dp[0][1] = k\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i - 1][1]\n",
    "            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)\n",
    "        \n",
    "        return sum(dp[-1])\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\"\n",
    "        设dp[i] := 涂i个柱子的方案数\n",
    "        1. 当前柱子与上一个颜色不同，则有k - 1种选择，方案数 = (k - 1) * dp[i - 1]\n",
    "        2. 当前柱子与上一个颜色相同，则有1种选择，但是i - 1与i - 2柱子颜色不相同，方案数 = (k - 1) * dp[i - 2]， 由(1)可得。\n",
    "\n",
    "        -> dp[i] = (k - 1) * (dp[i - 1] + dp[i - 2])\n",
    "        \"\"\"\n",
    "\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i == 1:\n",
    "                return k\n",
    "            \n",
    "            if i == 2:\n",
    "                return k * k\n",
    "            \n",
    "            return (k - 1) * (dp(i - 1) + dp(i - 2))\n",
    "\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dq=[[0 for _ in range(2)]for j in range(n)]\n",
    "        dq[0][0]=k  \n",
    "        dq[0][1]=0\n",
    "        for i in range(1,n):\n",
    "            dq[i][0]=dq[i-1][0]*(k-1)+dq[i-1][1]*(k-1)\n",
    "            dq[i][1]=dq[i-1][0]\n",
    "        print(dq)\n",
    "        return dq[-1][0]+dq[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if not n or not k: return 0\n",
    "\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        dp[0] = [k, 0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = (k - 1) * sum(dp[i - 1])\n",
    "            dp[i][1] = dp[i - 1][0]\n",
    "\n",
    "        return sum(dp[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        #[n][k][2]\n",
    "        dp=[[None,None]  for _ in range(n)]\n",
    "        dp[0][0]=1\n",
    "        dp[0][1]=0\n",
    "        for i in range(1,n):\n",
    "            dp[i][1]=dp[i-1][0]\n",
    "            dp[i][0]=(dp[i-1][0]+dp[i-1][1])*(k-1)\n",
    "                \n",
    "        return (dp[n-1][0]+dp[n-1][1])*k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n==0 or k == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        \n",
    "        same = [0] * (n+1)\n",
    "        diff = [0] * (n+1)\n",
    "\n",
    "        same[1] = 0\n",
    "        diff[1] = k\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            same[i] = diff[i-1]\n",
    "            diff[i] = same[i-1] * (k-1) + diff[i-1] * (k-1)\n",
    "        return same[n] + diff[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,num):\n",
    "            if i==n:\n",
    "                return 1\n",
    "            if num<2:\n",
    "                return (k-1)*dfs(i+1,1)+dfs(i+1,num+1)\n",
    "            else:\n",
    "                return (k-1)*dfs(i+1,1)\n",
    "\n",
    "        x = dfs(0,0)\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        dp = [ 0 ] * 2\n",
    "        dp[0], dp[1] = 0, k\n",
    "        for i in range(1, n):\n",
    "            dp[0], dp[1] = dp[1], (dp[0] + dp[1]) * ( k - 1 )\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [ 0 ] * 2\n",
    "        dp[0], dp[1] = 0, k\n",
    "        for i in range(1, n):\n",
    "            dp[0], dp[1] = dp[1], (dp[0] + dp[1]) * ( k - 1 )\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        if n == 2:\n",
    "            return k ** 2\n",
    "        if n > 2:\n",
    "            state = [0]*n\n",
    "            state[0] = k\n",
    "            state[1] = k * k\n",
    "            for i in range(2, n):\n",
    "                state[i] = (k-1)*state[i-2] + (k-1)*state[i-1]\n",
    "            # print(state)\n",
    "            return state[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dp = [1] * (n+2)\n",
    "        dp[1] = k\n",
    "        dp[2] = k + (k-1) * k \n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = (k-1) * dp[i-1] + (k-1) * dp[i-2]\n",
    "        return dp[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dp = [0]*(n+3)\n",
    "        dp[1]=k\n",
    "        dp[2]=k*k\n",
    "        if n<3:\n",
    "            return dp[n]\n",
    "\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = (k-1)*(dp[i-1]+dp[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def numWays(self, n: int, k: int) -> int:\n",
    "       if n == 1:\n",
    "           return k\n",
    "       \n",
    "       two_posts_back = k\n",
    "       one_post_back = k * k\n",
    "       \n",
    "       for i in range(3, n + 1):\n",
    "           curr = (k - 1) * (one_post_back + two_posts_back)\n",
    "           two_posts_back = one_post_back\n",
    "           one_post_back = curr\n",
    "\n",
    "       return one_post_back"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def numWays(self, n: int, k: int) -> int:\n",
    "       def total_ways(i):\n",
    "           if i == 1:\n",
    "               return k\n",
    "           if i == 2:\n",
    "               return k * k\n",
    "           \n",
    "           # 检查我们是否已经计算了 totalWays(i)\n",
    "           if i in memo:\n",
    "               return memo[i]\n",
    "           \n",
    "           # 使用递推关系计算 total_ways(i)\n",
    "           memo[i] = (k - 1) * (total_ways(i - 1) + total_ways(i - 2))\n",
    "           return memo[i]\n",
    "\n",
    "       memo = {}\n",
    "       return total_ways(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        if n == 2:\n",
    "            return k * k\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = k\n",
    "        dp[1] = k * k\n",
    "        for i in range(2, n):\n",
    "            dp[i] = (dp[i-2] + dp[i-1]) * (k - 1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0 \n",
    "        if n == 1:\n",
    "            return k \n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        dp[0][0] = k \n",
    "        dp[0][1] = k\n",
    "        dp[1][0] = k*(k-1)\n",
    "        dp[1][1] = k \n",
    "        \n",
    "        for i in range(2, n):\n",
    "            dp[i][0] = (k-1) * dp[i-1][0] + (k-1) * dp[i-1][1]\n",
    "            dp[i][1] = dp[i-1][0]\n",
    "\n",
    "        return sum(dp[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        # dp[n][0] n结尾，不连续\n",
    "        # dp[n][1] n结尾，连续\n",
    "        dp = [[0,0] for _ in range(n+1)]\n",
    "        dp[1][0] = k\n",
    "        dp[1][1] = 0 # 连续要两个\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            dp[i][0] = (dp[i-1][0] + dp[i-1][1]) * (k-1)\n",
    "            dp[i][1] = dp[i-1][0]\n",
    "        \n",
    "        return dp[-1][0] + dp[-1][1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        same, diff = k, k * (k-1)\n",
    "        for i in range(3, n+1):\n",
    "            same, diff = diff, (same + diff) * (k-1)\n",
    "        return same + diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        # # 动态规划\n",
    "        # dp = [0] * n\n",
    "        # for i in range(n):\n",
    "        #     if i == 0:      # 第一个栅栏\n",
    "        #         dp[i] = k\n",
    "        #     elif i == 1:    # 第二个栅栏\n",
    "        #         dp[i] = k * k\n",
    "        #     else:           # 第i个栅栏\n",
    "        #         dp[i] = dp[i - 2] * (k - 1) + dp[i - 1] * (k - 1)\n",
    "        # return dp[-1]\n",
    "\n",
    "        # 动态规划\n",
    "        if n == 1: return k\n",
    "        dp = [0] * n\n",
    "        dp[0], dp[1] = k, k * k\n",
    "        for i in range(2, n):\n",
    "            dp[i] = dp[i - 2] * (k - 1) + dp[i - 1] * (k - 1)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        dp[0][0] = k \n",
    "        dp[0][1] = 0 \n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] * (k-1) + dp[i-1][1] * (k-1)\n",
    "            dp[i][1] = dp[i-1][0] \n",
    "        return dp[n-1][0] + dp[n-1][1] \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        \n",
    "        dp = [[0]*2 for _ in range(2)]\n",
    "        dp[0][0]=k\n",
    "        for i in range(1,n):\n",
    "            dp[i%2][0] = (dp[(i+1)%2][0]+dp[(i+1)%2][1])*(k-1)\n",
    "            dp[i%2][1] = dp[(i+1)%2][0]\n",
    "        return sum(dp[(n+1)%2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        return self.answer_1(n, k)\n",
    "\n",
    "    def answer_1(self, n, k):\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def _dfs(i):\n",
    "            if i == 1:\n",
    "                return k\n",
    "            if i == 2:\n",
    "                return k * k\n",
    "\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "\n",
    "            memo[i] = (k - 1) * (_dfs(i - 1) + _dfs(i - 2))\n",
    "            return memo[i]\n",
    "\n",
    "        return _dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return k\n",
    "        if n==2:\n",
    "            return k**2\n",
    "        dp = [[0]*k for _ in range(n)]\n",
    "\n",
    "        for kk in range(k):\n",
    "            dp[0][kk] = 1\n",
    "        for kk in range(k):\n",
    "            dp[1][kk] = k\n",
    "        \n",
    "        for i in range(2, n):\n",
    "            for kk in range(k):\n",
    "                # ith bar if painted the same as previous bar\n",
    "                dp[i][kk] += sum(dp[i-2][:kk])+sum(dp[i-2][kk+1:])\n",
    "                \n",
    "                # ith bar is painted different from previous bar\n",
    "                dp[i][kk] += sum(dp[i-1][:kk])+sum(dp[i-1][kk+1:])\n",
    "        return sum(dp[-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n==1:\n",
    "            return k\n",
    "        if n==2:\n",
    "            return k*k\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=k\n",
    "        dp[2]=k*k\n",
    "\n",
    "        for i in range(3,n+1):\n",
    "            dp[i]=dp[i-2]*(k-1)+dp[i-1]*(k-1)\n",
    "\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        dp = [[0 for _ in range(2)] for _ in range(n)]\n",
    "        dp[0][1] = k\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i - 1][1]\n",
    "            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)\n",
    "        return dp[-1][0] + dp[-1][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        elif n == 2:\n",
    "            k * k\n",
    "        diff, same = k * (k -1), k \n",
    "        for i in range(2, n):\n",
    "            same, diff = diff, same * (k - 1) + diff * (k - 1)\n",
    "            # print(same, diff)\n",
    "        return same + diff "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        s, d = 0, k\n",
    "        for i in range(1, n):\n",
    "            t = s + d\n",
    "            s = d\n",
    "            d = t * (k - 1)\n",
    "        return s + d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        # gpt解答\n",
    "        # 动态规划不一定要使用二维数组\n",
    "        # 主要是迭代的逻辑\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        \n",
    "        same = 0\n",
    "        diff = k\n",
    "        \n",
    "        for i in range(2, n+1):\n",
    "            new_same = diff\n",
    "            new_diff = (k - 1) * (same + diff)\n",
    "            same = new_same\n",
    "            diff = new_diff\n",
    "        \n",
    "        return same + diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def numWays(self, n: int, k: int) -> int:\n",
    "       @lru_cache(None)\n",
    "       def total_ways(i):\n",
    "           if i == 1: \n",
    "               return k\n",
    "           if i == 2: \n",
    "               return k * k\n",
    "           \n",
    "           return (k - 1) * (total_ways(i - 1) + total_ways(i - 2))\n",
    "       \n",
    "       return total_ways(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return  k\n",
    "        dp = [0] * n\n",
    "        dp[0] = k\n",
    "        dp[1] = k*k\n",
    "        for i in range(2, n):\n",
    "            dp[i] = dp[i-2] * (k-1) + dp[i-1] * (k-1)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "\n",
    "        if n == 1: return k\n",
    "        if n == 2: return k*k\n",
    "        dp = [k for _ in range(n)]\n",
    "        dp[1] = k*k\n",
    "\n",
    "        for i in range(2, n):\n",
    "            dp[i] = (k-1) * (dp[i-1] + dp[i-2])\n",
    "        \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return k\n",
    "        if n == 2:\n",
    "            return k*k\n",
    "\n",
    "        dp = [0] * n\n",
    "        dp[0] = k\n",
    "        dp[1] = k*k\n",
    "\n",
    "        for i in range(2,n):\n",
    "            dp[i] = dp[i-2]*(k-1) + dp[i-1]*(k-1)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = k\n",
    "        dp[1] = k*k\n",
    "        for i in range(2, n):\n",
    "            dp[i] = (dp[i-1] + dp[i-2])*(k-1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        dp = [ 0 ] * 2\n",
    "        dp[0] = 0\n",
    "        dp[1] = k\n",
    "        for i in range(1, n):\n",
    "            dp[0], dp[1] = dp[1], (dp[0] + dp[1]) * ( k - 1 )\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return k\n",
    "        dp = [ [ 0 ] * 2 for _ in range(n) ]\n",
    "        dp[0][1] = k\n",
    "        dp[1][1] = k * (k-1)\n",
    "        dp[1][0] = k\n",
    "        for i in range(2, n):\n",
    "            dp[i][0] = dp[i-1][1]\n",
    "            dp[i][1] = (dp[i-1][0] + dp[i-1][1]) * (k-1)\n",
    "        return sum(dp[n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        @cache\n",
    "        #cnt : 最多连续\n",
    "        def dfs(i: int) -> int:\n",
    "            #boundary\n",
    "            if i == 1:\n",
    "                return k\n",
    "            if i == 2:\n",
    "                return k * k\n",
    "            #?\n",
    "            res = 0\n",
    "            #where\n",
    "            return (k - 1) * dfs(i - 1) + (k - 1) * dfs(i - 2) \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        k_2 = k\n",
    "        k_1 = k*k\n",
    "        for i in range(2, n):\n",
    "            k_0 = (k-1) * (k_1 + k_2)\n",
    "            k_2 = k_1\n",
    "            k_1 = k_0\n",
    "        if n == 1:\n",
    "            return k_2\n",
    "        return k_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 0: return 0\n",
    "        same = [0]*(n)\n",
    "        diff = [k]*(n)\n",
    "        for i in range(1, n):\n",
    "            same[i] = diff[i-1]\n",
    "            diff[i] = same[i-1]*(k-1) + diff[i-1]*(k-1)\n",
    "        return same[-1]+diff[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def numWays(self, n: int, k: int) -> int:\n",
    "       @lru_cache(None)\n",
    "       def total_ways(i):\n",
    "           if i == 1: \n",
    "               return k\n",
    "           if i == 2: \n",
    "               return k * k\n",
    "           \n",
    "           return (k - 1) * (total_ways(i - 1) + total_ways(i - 2))\n",
    "       \n",
    "       return total_ways(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "      @lru_cache(None)\n",
    "      def total_ways(i):\n",
    "        if i == 1:\n",
    "          return k\n",
    "        if i == 2:\n",
    "          return k * k\n",
    "        return (k-1)*(total_ways(i-1)+total_ways(i-2))\n",
    "      return total_ways(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        def  total_ways(i):\n",
    "            if i == 1:\n",
    "                return k\n",
    "            if i == 2:\n",
    "                return k*k\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            \n",
    "            memo[i] = (k-1)*(total_ways(i-1) + total_ways(i-2))\n",
    "            return memo[i]\n",
    "\n",
    "        memo={}\n",
    "        return total_ways(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return k\n",
    "        \n",
    "        result = [[0] * 2 for _ in range(n)]\n",
    "        # index 0: follow the pre color\n",
    "        # index 1: don't follow the pre color\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                result[i][0] = k\n",
    "                result[i][1] = k\n",
    "            elif i == 1:\n",
    "                result[i][0] = k\n",
    "                result[i][1] = (k - 1) * result[i][0]\n",
    "            else:\n",
    "                result[i][0] = result[i - 1][1]\n",
    "                result[i][1] = (result[i - 1][0] + result[i - 1][1]) * (k - 1)\n",
    "        \n",
    "        return result[-1][0] + result[-1][1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "        # dp[i][j]表示第i个栅栏涂第j种颜色的方案数\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 1: return k\n",
    "            elif i == 2: return k * k \n",
    "            else:\n",
    "                ans = (k - 1) * dfs(i - 1) + (k - 1) * dfs(i - 2)\n",
    "            return ans\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWays(self, n: int, k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i:int):\n",
    "            nonlocal k\n",
    "            if i ==1 :\n",
    "                return k\n",
    "            if i == 2:\n",
    "                return k *k\n",
    "            ans = (dfs(i-1)+ dfs(i-2))*(k-1)\n",
    "            return ans \n",
    "\n",
    "        return dfs(n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
